package 剑指offer;
//0729
//    作者：MisterBooo
//            链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/tu-jie-jian-zhi-offerzhi-er-wei-shu-zu-de-cha-zhao/
//            来源：力扣（LeetCode）
//            著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public class 二维数组的查找 {
    //@author:程序员吴师兄
//    如果当前位置元素比target小，则row++
//    如果当前位置元素比target大，则col--
//    如果相等，返回true
//    如果越界了还没找到，说明不存在，返回false
    public class Solution {
        public boolean Find(int target, int [][] array) {
            //边界条件判断
            if (array == null || array.length == 0 ||
                    array[0] == null || array[0].length == 0)
                return false;
            //获取函数矩阵的行数 m 与列数 n
            int m = array.length, n = array[0].length;
            //初始化一开始的元素位置，这里我们设置为矩阵最右上角的元素
            int i = 0, j = n - 1;
            //循环遍历整个函数
            while (i < m && j >= 0) {
                //如果目标值小于右上角的数字，则列下标减一
                if (target < array[i][j]) j--;
                    //如果目标值大于右上角的数字，则行下标加一
                else if (target > array[i][j]) i++;
                    //如果相等，直接 true
                else return true;
            }
            //循环结束后如果还没有找到目标时，返回 false
            return false;
        }
    }
/*
* 时间复杂度：O(n+m) 。 在循环语句中，除非直接返回结果，否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列，因此循环终止之前，循环不会运行超过 n+m 次。其它的操作都是常数，所以总的时间复杂度是线性的。
空间复杂度：O(1)。没有使用额外的存储空间，所以它的内存占用是恒定的。

* */
}
/*
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;

    }
}
* */
//class Solution {
//    public boolean findNumberIn2DArray(int[][] array, int target) {
//        //边界条件判断
//        if (array == null || array.length == 0 ||
//                array[0] == null || array[0].length == 0)
//            return false;
//        //获取函数矩阵的行数 m 与列数 n
//        int m = array.length, n = array[0].length;
//        //初始化一开始的元素位置，这里我们设置为矩阵最右上角的元素
//        int i = 0, j = n - 1;
//        //循环遍历整个函数
//        while (i < m && j >= 0) {
//            //如果目标值小于右上角的数字，则列下标减一
//            if (target < array[i][j]) j--;
//                //如果目标值大于右上角的数字，则行下标加一
//            else if (target > array[i][j]) i++;
//                //如果相等，直接 true
//            else return true;
//        }
//        //循环结束后如果还没有找到目标时，返回 false
//        return false;
//
//    }
//}